package 力扣_中等题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 连安利
 * @version 1.0
 * @date 2021/3/31 16:11
 */
public class 全排列 {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if(len == 0){
            return res;
        }
        boolean used[] = new boolean[len];//boolean数组初始化默认为false
        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, used, res);
        return res;

    }
    public void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used,
                    List<List<Integer>> res){
        if(depth == len ){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < len; i++){
            if(!used[i]){
                path.add(nums[i]);
                used[i] = true;
//                注意：这里的 depth+1 不能写成 depth++，这样就会直接改变depth的值
                dfs(nums, len, depth+1, path, used, res);

//                回溯
                 used[i] = false;
                 path.remove(path.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        全排列 test = new 全排列();
        int[] nums = {1,2,3};
        System.out.println(test.permute(nums));
    }
}
